package algorithms;

import org.junit.Test;

import javax.jws.Oneway;
import java.util.*;

/**
 * @功能
 * @创建时间 2020/6/6
 * 二项分布
 * CNk*p^k*(1-p)^(N-k)=(1-p)*C(N-1)k*p^k*(1-p)^(N-1-k)+p*C(N-1)(k-1)*p^(k-1)*(1-p)^(N-k)
 */
public class Binomial {
    public static List<Integer> findSubstring(String s, String[] words) {
        if (words.length == 0) {
            return null;
        }
        String a = "";
        HashMap<String,Integer> map = new HashMap<String,Integer>();
//        build(map, Arrays.asList(words),a);
        int len = words[0].length();
        for (int i = 0; i < words.length; i++) {

            map.put(words[i],map.get(words[i]) == null?0:map.get(words[i])+1);


        }
        List<Integer> res = new ArrayList<>();
        boolean isOver = true;
        for (int i = 0; i < s.length(); i++) {
            Map<String,Integer> map1 = (Map<String, Integer>) map.clone();
            for(int j = i;j<s.length();j+=len){
                if(j + len > s.length()){
                    break;
                }
                String tp = s.substring(j,j+len);
                if(map1.get(tp) != null ){
                    if(map1.get(tp) == 0){
                        map1.remove(tp);
                    }else {
                        map1.put(tp,map1.get(tp) - 1);
                    }

                } else {
                    break;
                }

            }
            if(map1.size() == 0){
                res.add(i);
            }

            }




        return res;
    }
    public static void build(Map<String, Integer> map, List<String> words, String a){
        if (words.size() == 0) {

            map.put(a,map.get(a)+1);
        }
        for (int i = 0; i < words.size(); i++) {

            List<String> tmp = new ArrayList<>();
            tmp.addAll(words);
            String b = a;
            b+=tmp.get(i);
            tmp.remove(i);
            build(map,tmp,b);
        }



    }

    public static void test(){

//        String a = "[\"foo\",\"bar\"]";
//        List<String> b = new ArrayList<>();
//        b.add("foo");
//        b.add("bar");
//        String[] c = new String[4];
//        c[0] = "word";
//        c[1] = "good";
//        c[2] = "best";
//        c[3] = "good";
//        findSubstring("wordgoodgoodgoodbestword",  c);
        Map<String,Object> map= new HashMap<>();


//        build(map,b,"");
//        System.err.println(map);
    }
    public static int waysToPartition(int[] nums, int k) {
        int len = nums.length;
        int[] sum = new int[len];
        for(int i = 0;i<len;i++){
            if(i > 0){
                sum[i] = nums[i] + sum[i - 1];
            }else {
                sum[i] = nums[i];
            }
        }
        int max = 0;
        for(int i = 0; i< len ;i++){
            if(sum[i] *2 == sum[len - 1]){
                max++;
            }
        }
        for(int i = 0;i<len ;i++){
            int matmp = 0;

            int dis = k - nums[i] ;
            for(int j = 0;j < len ;j++){
                if(j < i){
                    if(sum[j] *2 == sum[len - 1] + dis){
                        matmp++;
                    }
                } /*else if(j == i){
                    if(2*dis == sum[len - 1] + dis){
                        matmp++;
                    }
                }*/
            else{
                    if((sum[j] + dis) *2 == sum[len - 1] + dis){
                        matmp++;
                    }
                }
            }
            max = max > matmp ? max : matmp;
        }

        return max;

    }
//    public void www(){
//        final int MODULO = 1000000007;
//        int length = nums.length;
//        int[] counts = new int[length];
//        for (int[] request : requests) {
//            int start = request[0], end = request[1];
//            counts[start]++;
//            if (end + 1 < length) {
//                counts[end + 1]--;
//            }
//        }
//        for (int i = 1; i < length; i++) {
//            counts[i] += counts[i - 1];
//        }
//        Arrays.sort(counts);
//        Arrays.sort(nums);
//        long sum = 0;
//        for (int i = length - 1; i >= 0 && counts[i] > 0; i--) {
//            sum += (long) nums[i] * counts[i];
//        }
//        return (int) (sum % MODULO);
//
//    }
    public static void main(String[] args) {
 //       int x = 10000*10000;
        int[] a = {0,0,0,0,0,0,0,0,0,-4732,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
   //     long x = (long) Integer.MAX_VALUE*10;
        System.err.println(waysToPartition(a,-4732));
    //    test();
    //    System.out.println(binomial1(100,50,0.25));
    }
    public static double binomial1(int n,int k,double p){
        if(n==0&&k==0)
            return 1.0;
        if(n<0||k<0)
            return 0.0;
        return (1.0-p)*binomial1(n-1,k,p)+p*binomial1(n-1,k-1,p);
    }
    //省去了重复的运算
    public static double binomial2(int N,int k,double p)
    {
        if (N < 0 || k < 0) return 0.0;
        double[][] ret = new double[N + 1][k + 1];
        //完成递归版第一步
        ret[0][0] = 1.0;
        //完成递归版第二步
        for (int i = 1; i < N + 1; ++i)
        {
            ret[i][0] = ret[i - 1][0] * (1.0 - p);
        }
        for (int j = 1; j < k + 1; ++j)
        {
            ret[0][j] = 0.0;
        }
        //得到序列ret[N][k]
        //完成递归版第三步
        for (int i = 1; i < N + 1; ++i)
            for (int j = 1; j < k + 1;++j)
            {
                ret[i][j] = (1.0 - p) * ret[i - 1][j] + p * ret[i - 1][j - 1];
            }
        return ret[N][k];
    }
    //计算组合数
    public static double combination(double N, double k)
    {
        double min = k;
        double max = N-k;
        double t = 0;

        double NN=1;
        double kk=1;

        if(min>max){
            t=min;
            min = max;
            max=t;
        }

        while(N>max){//分母中较大的那部分阶乘约分不用计算
            NN=NN*N;
            N--;
        }

        while(min>0){//计算较小那部分的阶乘
            kk=kk*min;
            min--;
        }

        return NN/kk;
    }

    //计算二项分布值（硬算）
    public static double binomial3(int N,int k,double p)
    {
        double a=1;
        double b=1;

        double c =combination(N,k);

        while((N-k)>0){  //计算(1-p)的(N-k)次方
            a=a*(1-p);
            N--;
        }

        while(k>0){  //计算p的k次方
            b=b*p;
            k--;
        }

        return c*a*b;
    }


}
